#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>

struct Node {
   int val;
   struct Node* next;
   struct Node* random;
};

struct Node* BuyNode(int x)
{
    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->val = x;
    newnode->next = NULL;
    newnode->random = NULL;

    return newnode;
}

struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
        return NULL;

    struct Node* cur = head;
    struct Node* curNext = cur->next;

    struct Node* newnode = BuyNode(cur->val);

    while (cur != NULL)
    {
        newnode = BuyNode(cur->val);

        cur->next = newnode;
        newnode->next = curNext;

        cur = curNext;
        if (curNext != NULL)
            curNext = curNext->next;
    }

    cur = head;
    struct Node* copy = cur->next;

    while (1)
    {
        if (cur->random != NULL)
            copy->random = cur->random->next;
        else
            copy->random = NULL;

        cur = cur->next->next;
        if (cur == NULL)
            break;
        copy = copy->next->next;
    }

    cur = head;
    struct Node* newhead = cur->next;
    struct Node* newcur = newhead;

    while (cur->next->next != NULL)
    {
        cur = cur->next->next;
        newcur->next = cur->next;
        newcur = cur->next;
    }

    return newhead;
}

int main()
{
    struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* n4 = (struct Node*)malloc(sizeof(struct Node));
    struct Node* n5 = (struct Node*)malloc(sizeof(struct Node));
    n1->val = 7;
    n2->val = 13;
    n3->val = 11;
    n4->val = 10;
    n5->val = 1;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = NULL;
    n1->random = NULL;
    n2->random = n1;
    n3->random = n5;
    n4->random = n3;
    n5->random = n1;


    copyRandomList(n1);
    return 0;
}



//
//
//#include<stdio.h>
//#include<stdlib.h>
//
// struct Node {
//     int val;
//     struct Node *next;
//     struct Node *random;
// };
// 
//
//struct Node* BuyNode(int x)
//{
//    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
//    newnode->val = x;
//    newnode->next = NULL;
//    newnode->random = NULL;
//
//    return newnode;
//}
//
//struct Node* copyRandomList(struct Node* head)
//{
//    struct Node* cur = head;
//    struct Node* curNext = cur->next;
//    struct Node* newhead = BuyNode(cur->val);
//    struct Node* newCur = newhead;
//    struct Node* newCurNext = BuyNode(curNext->val);
//
//    while (1)
//    {
//        newCur->next = newCurNext;
//
//        if (curNext->next != NULL)
//            curNext = curNext->next;
//        else
//            break;
//
//        newCur = newCurNext;
//        newCurNext = BuyNode(curNext->val);
//
//    }
//
//
//}
//
//int main()
//{
//    struct Node* n1 = (struct Node*)malloc(sizeof(struct Node));
//    struct Node* n2 = (struct Node*)malloc(sizeof(struct Node));
//    struct Node* n3 = (struct Node*)malloc(sizeof(struct Node));
//    struct Node* n4 = (struct Node*)malloc(sizeof(struct Node));
//    struct Node* n5 = (struct Node*)malloc(sizeof(struct Node));
//    n1->val = 1;
//    n2->val = 2;
//    n3->val = 3;
//    n4->val = 4;
//    n5->val = 5;
//    n1->next = n2;
//    n2->next = n3;
//    n3->next = n4;
//    n4->next = n5;
//    n5->next = NULL;
//
//
//
//    copyRandomList(n1);
//    return 0;
//}